{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Diet Plan Performance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: dietPlanPerformance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #健身计划评估"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你的好友是一位健身爱好者。前段日子，他给自己制定了一份健身计划。现在想请你帮他评估一下这份计划是否合理。</p>\n",
    "\n",
    "<p>他会有一份计划消耗的卡路里表，其中&nbsp;<code>calories[i]</code>&nbsp;给出了你的这位好友在第&nbsp;<code>i</code>&nbsp;天需要消耗的卡路里总量。</p>\n",
    "\n",
    "<p>为了更好地评估这份计划，对于卡路里表中的每一天，你都需要计算他 「这一天以及之后的连续几天」 （共&nbsp;<code>k</code> 天）内消耗的总卡路里 <em>T：</em></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果&nbsp;<code>T &lt; lower</code>，那么这份计划相对糟糕，并失去 1 分；&nbsp;</li>\n",
    "\t<li>如果 <code>T &gt; upper</code>，那么这份计划相对优秀，并获得 1 分；</li>\n",
    "\t<li>否则，这份计划普普通通，分值不做变动。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请返回统计完所有&nbsp;<code>calories.length</code>&nbsp;天后得到的总分作为评估结果。</p>\n",
    "\n",
    "<p>注意：总分可能是负数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>calories = [1,2,3,4,5], k = 1, lower = 3, upper = 3\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>calories[0], calories[1] &lt; lower 而 calories[3], calories[4] &gt; upper, 总分 = 0.</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>calories = [3,2], k = 2, lower = 0, upper = 1\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>calories[0] + calories[1] &gt; upper, 总分 = 1.\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>calories = [6,5,0,0], k = 2, lower = 1, upper = 5\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>calories[0] + calories[1] &gt; upper, calories[2] + calories[3] &lt; lower, 总分 = 0.\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= calories.length &lt;= 10^5</code></li>\n",
    "\t<li><code>0 &lt;= calories[i] &lt;= 20000</code></li>\n",
    "\t<li><code>0 &lt;= lower &lt;= upper</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [diet-plan-performance](https://leetcode.cn/problems/diet-plan-performance/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [diet-plan-performance](https://leetcode.cn/problems/diet-plan-performance/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5]\\n1\\n3\\n3', '[3,2]\\n2\\n0\\n1', '[6,5,0,0]\\n2\\n1\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:\n",
    "        win_score = 0\n",
    "        lose_score = 0\n",
    "        total = sum(calories[:k])\n",
    "        if(total>upper):\n",
    "            win_score=1\n",
    "        if(total<lower):\n",
    "            lose_score=-1\n",
    "        \n",
    "        for i in range(k, len(calories)):\n",
    "            total = total + calories[i]-calories[i-k]\n",
    "            if (total > upper ):\n",
    "                win_score += 1\n",
    "            elif (total < lower):\n",
    "                lose_score -= 1\n",
    "        print(win_score,lose_score)\n",
    "        return win_score+lose_score\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:\n",
    "        n=len(calories)\n",
    "        cur=0\n",
    "        ans=0\n",
    "        for i in range(k):\n",
    "            cur+=calories[i]\n",
    "        if cur<lower:\n",
    "            ans-=1\n",
    "        if cur>upper:\n",
    "            ans+=1\n",
    "        for i in range(k,n):\n",
    "            cur+=calories[i]\n",
    "            cur-=calories[i-k]\n",
    "            if cur<lower:\n",
    "                ans-=1\n",
    "            if cur>upper:\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:\n",
    "        n=len(calories)\n",
    "        ret=0\n",
    "        i,j=0,k-1\n",
    "        now=sum(calories[:k])\n",
    "        while j<n:\n",
    "            if now>upper:\n",
    "                ret+=1\n",
    "            if now<lower:\n",
    "                ret-=1\n",
    "            now-=calories[i]\n",
    "            j+=1\n",
    "            if j<n:\n",
    "                now+=calories[j]\n",
    "            i+=1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:\n",
    "        win_score = 0\n",
    "        lose_score = 0\n",
    "        total = sum(calories[:k])\n",
    "        if (total > upper):\n",
    "            win_score = 1\n",
    "        if (total < lower):\n",
    "            lose_score = -1\n",
    "\n",
    "        for i in range(k, len(calories)):\n",
    "            total = total + calories[i]-calories[i-k]\n",
    "            if (total > upper):\n",
    "                win_score += 1\n",
    "            elif (total < lower):\n",
    "                lose_score -= 1\n",
    "        print(win_score + lose_score)\n",
    "        return win_score+lose_score\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:\n",
    "        def getpoints(sum, lower, upper):\n",
    "            points = 0\n",
    "            if sum > upper:\n",
    "                points += 1\n",
    "            elif sum < lower:\n",
    "                points -= 1\n",
    "            return points\n",
    "        \n",
    "        sum = 0\n",
    "        for i in range(k):\n",
    "            sum += calories[i]\n",
    "        \n",
    "        points = 0\n",
    "        points += getpoints(sum, lower, upper)\n",
    "        for i in range(k, len(calories)):\n",
    "            sum += calories[i]\n",
    "            sum -= calories[i - k]\n",
    "            points += getpoints(sum, lower, upper)\n",
    "        return points"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:\n",
    "        total = sum(calories[:k])\n",
    "        m = 0\n",
    "        if total > upper:\n",
    "            m += 1\n",
    "        if total < lower:\n",
    "            m -= 1\n",
    "        for i in range(len(calories) - k):\n",
    "            total = total - calories[i] + calories[i + k]\n",
    "            if total > upper:\n",
    "                m += 1\n",
    "            if total < lower:\n",
    "                m -= 1\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:\n",
    "        total = sum(calories[:k])\n",
    "        m = 0\n",
    "        if total > upper:\n",
    "            m += 1\n",
    "        if total < lower:\n",
    "            m -= 1\n",
    "        for i in range(len(calories) - k):\n",
    "            total = total - calories[i] + calories[i + k]\n",
    "            if total > upper:\n",
    "                m += 1\n",
    "            if total < lower:\n",
    "                m -= 1\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:\n",
    "        t = sum(calories[:k])\n",
    "        r = 0\n",
    "        if t < lower:\n",
    "            r -= 1\n",
    "        elif t > upper:\n",
    "            r += 1\n",
    "        else:\n",
    "            pass\n",
    "\n",
    "        for i in range(1, len(calories)-k+1):\n",
    "            t -= calories[i-1]\n",
    "            t += calories[i-1+k]\n",
    "            if t < lower:\n",
    "                r -= 1\n",
    "            elif t > upper:\n",
    "                r += 1\n",
    "            else:\n",
    "                pass\n",
    "            #print(t)\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:\n",
    "\n",
    "        tmp = 0\n",
    "        res = 0\n",
    "        for i in range(k):\n",
    "            tmp += calories[i]\n",
    "        if tmp > upper:\n",
    "            res += 1\n",
    "        elif tmp < lower:\n",
    "            res -= 1\n",
    "        \n",
    "        for i in range(len(calories)-k):\n",
    "            tmp += calories[i+k] - calories[i]\n",
    "            if tmp > upper:\n",
    "                res += 1\n",
    "            elif tmp < lower:\n",
    "                res -= 1 \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:\n",
    "        ans = 0\n",
    "        sum = 0\n",
    "        for i in range(k):\n",
    "            sum += calories[i]\n",
    "        if sum < lower:\n",
    "            ans -= 1\n",
    "        elif sum > upper:\n",
    "            ans += 1\n",
    "        for i in range(k, len(calories)):\n",
    "            sum = sum + calories[i] - calories[i-k]\n",
    "            if sum < lower:\n",
    "                ans -= 1\n",
    "            elif sum > upper:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # Moving window. Time O(n) Space O(1)\n",
    "    def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:\n",
    "        n = len(calories)\n",
    "        res = 0\n",
    "        window = sum(calories[:k])\n",
    "        res += self.getPoint(window, lower, upper)\n",
    "        for i in range(k, n):\n",
    "            window += calories[i]\n",
    "            window -= calories[i-k]\n",
    "            res += self.getPoint(window, lower, upper)\n",
    "        return res\n",
    "\n",
    "    def getPoint(self, total, lower, upper):\n",
    "        if total > upper:\n",
    "            return 1\n",
    "        elif total < lower:\n",
    "            return -1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:\n",
    "        res=0\n",
    "        s=0\n",
    "        i=0\n",
    "        l=len(calories)\n",
    "        while i<l:\n",
    "            if i<k:\n",
    "                while i<k:\n",
    "                    s+=calories[i]\n",
    "                    i+=1\n",
    "            else:\n",
    "                s+=calories[i]\n",
    "                s-=calories[i-k]\n",
    "                i+=1\n",
    "            print(s,i)\n",
    "            if s>upper:\n",
    "                res+=1\n",
    "            elif s<lower:\n",
    "                res-=1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:\n",
    "        total = sum(calories[:k])\n",
    "        m = 0\n",
    "        if total > upper:\n",
    "            m += 1\n",
    "        if total < lower:\n",
    "            m -= 1\n",
    "        for i in range(len(calories) - k):\n",
    "            total = total - calories[i] + calories[i + k]\n",
    "            if total > upper:\n",
    "                m += 1\n",
    "            if total < lower:\n",
    "                m -= 1\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:\n",
    "        n = len(calories)\n",
    "        res = 0\n",
    "        cur = 0\n",
    "        for i in range(k):\n",
    "            cur += calories[i]\n",
    "        if cur < lower:\n",
    "            res -= 1\n",
    "        elif cur>upper:\n",
    "            res += 1\n",
    "        for i in range(1,n-k+1):\n",
    "            cur -= calories[i-1]\n",
    "            cur += calories[i+k-1]\n",
    "            if cur<lower:\n",
    "                res -=1 \n",
    "            elif cur>upper:\n",
    "                res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(calories)\n",
    "        s = sum(calories[:k])\n",
    "        if s > upper:\n",
    "            ans += 1\n",
    "        elif s < lower:\n",
    "            ans -= 1\n",
    "        for i in range(1, n - k + 1):\n",
    "            s += calories[i + k - 1]\n",
    "            s -= calories[i - 1]\n",
    "            if s > upper:\n",
    "                ans += 1\n",
    "            elif s < lower:\n",
    "                ans -= 1\n",
    "        return ans \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:\n",
    "        total = sum(calories[:k])\n",
    "        m = 0\n",
    "        if total > upper:\n",
    "            m += 1\n",
    "        if total < lower:\n",
    "            m -= 1\n",
    "        for i in range(len(calories) - k):\n",
    "            total = total - calories[i] + calories[i + k]\n",
    "            if total > upper:\n",
    "                m += 1\n",
    "            if total < lower:\n",
    "                m -= 1\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:\n",
    "        total = sum(calories[:k])\n",
    "        m = 0\n",
    "        if total > upper:\n",
    "            m += 1\n",
    "        if total < lower:\n",
    "            m -= 1\n",
    "        for i in range(len(calories) - k):\n",
    "            total = total - calories[i] + calories[i + k]\n",
    "            if total > upper:\n",
    "                m += 1\n",
    "            if total < lower:\n",
    "                m -= 1\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:\n",
    "        n = len(calories)\n",
    "        pre = ans = 0\n",
    "        for i in range(n):\n",
    "            pre += calories[i]\n",
    "            if i >= k-1:\n",
    "                if pre < lower:\n",
    "                    ans -= 1\n",
    "                elif pre > upper:\n",
    "                    ans += 1\n",
    "                pre -= calories[i-k+1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:\n",
    "        l,r,cur,res=0,0,0,0\n",
    "        while r<len(calories):\n",
    "            cur+=calories[r]\n",
    "            if r-l+1>=k:\n",
    "                if cur>upper:\n",
    "                    res+=1\n",
    "                if cur <lower:\n",
    "                    res-=1\n",
    "                cur-=calories[l]\n",
    "                l+=1\n",
    "            r+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:\n",
    "\n",
    "        res = 0\n",
    "        cur = 0\n",
    "        l,r = 0,0\n",
    "        while r<len(calories):\n",
    "            cur += calories[r]\n",
    "            if r-l+1>=k:\n",
    "                if cur>upper:\n",
    "                    res += 1\n",
    "                if cur <lower:\n",
    "                    res -=1\n",
    "                cur -= calories[l]\n",
    "                l+=1\n",
    "            r += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:\n",
    "        res = 0\n",
    "        l,r,cur = 0,0,0\n",
    "        while r<len(calories):\n",
    "            cur += calories[r]\n",
    "            if r-l+1>=k:\n",
    "                if cur>upper:\n",
    "                    res+=1\n",
    "                if cur<lower:\n",
    "                    res-=1\n",
    "                cur-=calories[l]\n",
    "                l+=1\n",
    "            r+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:\n",
    "        prefix = list(accumulate(calories, initial = 0))\n",
    "        res = 0\n",
    "        for i in range(k, len(prefix)):\n",
    "            if prefix[i] - prefix[i - k] > upper:\n",
    "                res += 1\n",
    "            elif prefix[i] - prefix[i - k] < lower:\n",
    "                res -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:\n",
    "        n = len(calories) \n",
    "        pre = [0] * (n+1)\n",
    "        for i in range(1, n+1):\n",
    "            pre[i] = pre[i-1] + calories[i-1]\n",
    "        def calc(l, k):\n",
    "            r = min(l + k, n)\n",
    "            return pre[r] - pre[l] \n",
    "        ans = 0\n",
    "        for i in range(n-k+1):\n",
    "            x = calc(i, k)\n",
    "            if x > upper:\n",
    "                ans += 1\n",
    "            elif x < lower:\n",
    "                ans -= 1\n",
    "        return ans "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
